/*
https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/solution/wan-cheng-suo-you-gong-zuo-de-zui-duan-s-hrhu/
 */
import java.util.Arrays;

public class Solution1723 {
    public int minimumTimeRequired(int[] jobs, int k) {
        Arrays.sort(jobs);
        int sum=0,max=0;
        for (int job : jobs) {
            max=Math.max(max,job);
            sum+=job;
        }
        int l=max,r=sum;
        int ans=0;
        while (l<=r){
            int mid=(l+r)/2;
            int[] f=new int[k];
            if (check(jobs,f,mid,jobs.length-1)){
                ans=mid;
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return ans;
    }

    boolean check(int[] jobs,int[] f,int limit,int t){
        if (t<0){
            return true;
        }
        int c=jobs[t];
        for (int i=0;i<f.length;i++) {
            if (f[i]+c<=limit){
                f[i]=f[i]+c;
                if (check(jobs,f,limit,t-1)){
                    return true;
                }
                f[i]=f[i]-c;
                if (f[i]==0 || f[i]+c==limit){
                    return false;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1723().minimumTimeRequired(new int[]{5,5,4,4,4},2));
    }
}
